1
Condizioni di Ottimalità per Vincoli di Uguaglianza
MATH008Lesson 10
00:00
Immagina un sistema fisico, come una catena appesa, che cerca il suo stato di energia più bassa. Se gli estremi sono fissi, il sistema non può muoversi liberamente. L'ottimalità è raggiunta quando le forze interne (il gradiente dell'energia potenziale) sono perfettamente bilanciate dalle forze di tensione esercitate dai vincoli. Nell'ottimizzazione convessa, questo equilibrio è catturato dalle condizioni di KKT per i vincoli di uguaglianza.

La Geometria della Fattibilità

Per un problema convesso con vincoli di uguaglianza $Ax=b$, un vettore $v \in \mathbf{R}^n$ è una direzione fattibile se $Av = 0$. Ciò significa che muoversi nella direzione $v$ preserva il vincolo: $A(x+v) = b$ se $Ax=b$.

Affinché $x^*$ sia ottimale, la derivata direzionale $\nabla f(x^*)^T v$ deve essere nulla per tutte le direzioni fattibili $v$ nello spazio nullo $\mathcal{N}(A)$. Ciò implica che il gradiente $\nabla f(x^*)$ deve essere ortogonale a $\mathcal{N}(A)$, portandoci all'esistenza dei moltiplicatori di Lagrange.

La Condizione di Ottimalità

Un punto $x^*$ è ottimale se e solo se esiste un vettore $\nu^* \in \mathbb{R}^p$ tale che:

$\nabla f(x^*) + A^T \nu^* = 0$

Questo forma un sistema di equazioni lineari che caratterizza l'equilibrio tra la discesa obiettivo e la varietà del vincolo.

Il Gradiente Proiettato

La proiezione euclidea del gradiente negativo $-\nabla f(x)$ sullo spazio nullo $\mathcal{N}(A)$ è data da:

$\Delta x_{\text{pg}} = \text{argmin}_{Au=0} \| -\nabla f(x) - u \|_2$

Questo vettore rappresenta la "migliore" direzione di discesa fattibile. Fondamentale, $x$ è ottimale se e solo se $\Delta x_{\text{pg}} = 0$.

Il Sistema di KKT e le Proprietà della Matrice

Possiamo risolvere simultaneamente per lo step di Newton e le variabili duali usando il sistema a blocchi:

$$\begin{bmatrix} I & A^T \\ A & 0 \end{bmatrix} \begin{bmatrix} v \\ w \end{bmatrix} = \begin{bmatrix} -\nabla f(x) \\ 0 \end{bmatrix}$$

Nota sulle proprietà spettrali della matrice: La matrice di KKT è simmetrica ma indeterminata. Se la matrice è non singolare, ha esattamente $n$ autovalori positivi e $p$ negativi. Ciò implica che il punto ottimale $(x^*, \nu^*)$ è un punto sella della funzione lagrangiana $L(x, \nu) = f(x) + \nu^T(Ax-b)$, piuttosto che un semplice minimo locale nello spazio primale-duale combinato.

🎯 Principio Fondamentale
L'ottimalità nei problemi con vincoli di uguaglianza richiede che il gradiente sia ortogonale allo spazio nullo del vincolo. Ciò ci permette di interpretare lo step di Newton come soluzione di un'approssimazione linearizzata delle condizioni di KKT.